#include <iostream>
using namespace std;

struct ListNode
{
    int val;
    int a;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

void add(ListNode *head, int val)
{
    while (head->next)
        head = head->next;
    ListNode *temp = new ListNode(val);
    head->next = temp;
}

ListNode *removeNthFromEnd(ListNode *head, int n)
{
    if (head == nullptr || head->next == nullptr)
        return nullptr;
    ListNode *a, *b, *temp = new ListNode(0, head);
    a = b = temp;
    while (n--)
        b = b->next;
    while (b->next)
        b = b->next, a = a->next;
    a->next = a->next->next;
    head = temp->next;
    delete temp;
    return head;
}

ListNode *mswap(ListNode *a)
{
    ListNode *temp;
    if (a->next == nullptr)
        return a;
    else
        temp = mswap(a->next);
    a->next->next = a;
    return temp;
}

ListNode *kswap(ListNode *head, int k)
{
    ListNode *b = head, *c = head;
    for (int i = 1; i < k && c != nullptr; c = c->next, i++)
        ;
    if (c == nullptr)
        return b;
    else
    {
        ListNode *temp = kswap(c->next, k);
        c->next = nullptr;
        mswap(b);
        b->next = temp;
        return c;
    }
}

class MyLinkedList
{
public:
    int val;
    MyLinkedList *next;
    MyLinkedList *pre;
    MyLinkedList *head;
    MyLinkedList *tail;

    MyLinkedList()
    {
        val = -1;
        head = nullptr;
        tail = nullptr;
        next = nullptr;
        pre = nullptr;
    }

    MyLinkedList(int _val)
    {
        val = _val;
        head = nullptr;
        tail = nullptr;
        next = nullptr;
        pre = nullptr;
    }
    int add();
    int get(int index)
    {
        if (!this->head)
            return -1;
        MyLinkedList *tmp = this->head;
        while (--index)
        {
            if (tmp == nullptr)
                return -1;
            tmp = tmp->next;
        }
        return tmp->val;
    }

    void addAtHead(int val)
    {
        MyLinkedList *temp = new MyLinkedList(val);
        if (this->head == nullptr)
        {
            this->head = temp;
            this->tail = temp;
        }
        else
        {
            temp->next = this->head;
            this->head->pre = temp;
            this->head = temp;
        }
    }

    void addAtTail(int val)
    {
        MyLinkedList *temp = new MyLinkedList(val);
        if (this->head == nullptr)
        {
            this->head = temp;
            this->tail = temp;
        }
        else
        {
            temp->pre = this->tail;
            this->tail->next = temp;
            this->tail = temp;
        }
    }

    void addAtIndex(int index, int val)
    {
        MyLinkedList *temp = new MyLinkedList(val);
        MyLinkedList *ptr = this->head;
        while (--index)
        {
            if (!ptr)
                return;
            ptr = ptr->next;
        }
        temp->next = ptr;
        if (ptr->pre != nullptr)
        {
            temp->pre = ptr->pre;
            ptr->pre->next = temp;
        }
        else
        {
            this->head = temp;
        }
        ptr->pre = temp;
    }

    void deleteAtIndex(int index)
    {
        MyLinkedList *ptr = this->head;
        while (--index)
        {
            if (!ptr)
                return;
            ptr = ptr->next;
        }
        if (ptr->pre != nullptr)
            ptr->pre->next = ptr->next;
        else
            this->head = ptr->next;
        if (ptr->next != nullptr)
            ptr->next->pre = ptr->pre;
        else
            this->tail = ptr->pre;
        delete ptr;
    }

    void print()
    {
        MyLinkedList *ptr = this->head;
        while (ptr != nullptr)
        {
            cout << ptr->val << " ";
            ptr = ptr->next;
        }
        cout << endl;
    }
};

int main()
{
    MyLinkedList *obj = new MyLinkedList();
    int param_1 = obj->get(1);
    cout << param_1 << endl;
    obj->addAtHead(1);
    obj->print();
    obj->addAtTail(3);
    obj->print();
    obj->addAtIndex(1, 2);
    obj->print();
    param_1 = obj->get(1);
    cout << param_1 << endl;
    obj->deleteAtIndex(1);
    obj->print();
    param_1 = obj->get(1);
    cout << param_1 << endl;
    return 0;
}